import copy
from typing import List


# 40. 组合总和 II
# 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
# candidates 中的每个数字在每个组合中只能使用 一次 。
def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    re = list()
    # 排序，从小到大
    candidates.sort()

    candidates_len = len(candidates)

    def back_track(current_index: int,
                    for_candidate: List[int],
                    temp_target: int,
                    current_list: List[int],
                    result_list: List[List[int]]):
        '''
        :param current_index:  当前数的下标
        :param for_candidate:  用这个数组减枝，循环的时候不会重复，达到【减枝】效果
        :param temp_target:  目标数
        :param current_list: 当前累加的集合
        :param result_list:  返回结果
        :return:
        '''

        # 无法继续往下找
        if temp_target < 0:
            return

        # 找到了数，可以立即返回，由于是排好序的数，无需继续往下找
        if temp_target == 0:
            copy_current_list = copy.copy(current_list)
            result_list.append(copy_current_list)
            return

        # temp_target > 0 ，需要继续往下找
        # 遍历每一个候选数
        for candidate_index in range(current_index, candidates_len):
            # 当前数
            candidate = candidates[candidate_index]

            if candidate in for_candidate:
                continue

            for_candidate.append(candidate)
            left = temp_target - candidate
            # 添加当前元素
            current_list.append(candidate)
            back_track(candidate_index + 1, [], left, current_list, result_list)
            # 移除最后一个元素，回溯
            current_list.pop()

    back_track(0, [], target, [], re)

    return re


candidates_1 = [1, 1, 1, 1, 1,
                1, 1, 1, 1, 1,
                1, 1, 1, 1, 1,
                1, 1, 1, 1, 1,
                1, 1, 1, 1, 1,
                1, 1]
target_1 = 27
result = combinationSum2(candidates_1, target_1)
print(f"result:{result}")

candidates_1 = [10, 1, 2, 7, 6, 1, 5]
target_1 = 8
result = combinationSum2(candidates_1, target_1)
print(f"result:{result}")

candidates_1 = [2, 5, 2, 1, 2]
target_1 = 5
result = combinationSum2(candidates_1, target_1)
print(f"result:{result}")
